/* https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：
+ 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
+ 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
* */
const myReverse = (head, tail) => { //head 和 tail 以及它们之间 一共有k个节点
  let prev = tail.next;  //之所以叫pre, 是因为整体反转过来后 最后的就是最前面的了
  //查看lc206
  //这里的prev 就是我们的↓这里的 p2, 只是相较于lc206比较特殊的是, 这里的node1要先指向node6 (即p2要指定为node6而不是像lc206一样开始置为null), 然后就和lc206一样了
  //↓p2  ↓p1 ---> 反转一次 就整体向右移动1
  //   | node1  node2  node3  node4  node5 | node6
  //     ↑head                        ↑tail
  let p = head; //相当于我们↑的p1
  while (prev !== tail) {
    const nex = p.next; // 先保存起来 交换完后 再让p1继续往下走
    p.next = prev;  //在此反转 // 比如k为3, 12345 -> 32145, 1要指向4

    prev = p; //p2向右移动1
    p = nex; //p1向右移动1
  }
  return [tail, head];
}
var reverseKGroup = function(head, k) {
  //虚拟头节点, 总是指向最新的链表的头
  const hair = new ListNode(0);
  hair.next = head;
  let pre = hair;

  while (head) {
    let tail = pre;
    // 查看剩余部分长度是否大于等于 k
    for (let i = 0; i < k; ++i) {
      tail = tail.next;
      if (!tail) {
        return hair.next;
      }
    }
    const nex = tail.next; //下一组的头节点
    [head, tail] = myReverse(head, tail); //得到当前组交换后的头和尾
    // 把子链表重新接回原链表
    pre.next = head; //当前组头节点的上一个节点 要指向当前组交换后的头结点
    tail.next = nex; //当前组交换后的尾要指向下一组的头
    pre = tail; //pre总是指向当前这一组的尾 下一组的头的前面一个节点
    head = tail.next; //head要指向下一组的头节点
  }
  return hair.next;
};
